home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C++ / Libraries / KPlib 1.2.1 / KPSet.h < prev    next >
Encoding:
Text File  |  1994-11-07  |  11.7 KB  |  172 lines  |  [TEXT/R*ch]
  1. // A module of KPlib v1.2.1.
  2. // Written by Keith Pomakis during the summer of 1994.
  3. // Released to the public domain on October 10, 1994.
  4.  
  5. #ifndef KP_SET_DEFINED
  6. #define KP_SET_DEFINED
  7.  
  8. #include "KPbasic.h"
  9. #include "KPList.h"
  10.  
  11. // Assumes Element has a default constructor, operator=(), operator==(),
  12. // and operator<().  Note that operator<() must place a total ordering on
  13. // the set of Elements.
  14.  
  15. // All union, intersection and difference operations are of order O(n).
  16.  
  17. template <class Element>
  18. class KPSet {
  19.     public:
  20.         KPSet();
  21.         KPSet(const KPSet &set);
  22.         KPSet(const KPList<Element> &list);
  23.         KPSet(const Element &element);
  24.         ~KPSet();
  25.         operator KPList<Element>() const;
  26.  
  27.         // Union
  28.         KPSet operator+(const KPSet &set) const;
  29.         KPSet operator+(const Element &element) const;
  30.         KPSet &operator+=(const KPSet &set);
  31.         KPSet &operator+=(const Element &element);
  32.         KPSet &add(const KPSet &set);
  33.         KPSet &add(const Element &element);
  34.  
  35.         // Intersection
  36.         KPSet operator*(const KPSet &set) const;
  37.         KPSet operator*(const Element &element) const;
  38.         KPSet &operator*=(const KPSet &set);
  39.         KPSet &operator*=(const Element &element);
  40.  
  41.         // Difference
  42.         KPSet operator-(const KPSet &set) const;
  43.         KPSet operator-(const Element &element) const;
  44.         KPSet &operator-=(const KPSet &set);
  45.         KPSet &operator-=(const Element &element);
  46.  
  47.         // Miscellaneous
  48.         KPSet &operator=(const KPSet &set);
  49.         KPSet &operator=(const Element &element);
  50.         KPSet &operator=(const KPList<Element> &list);
  51.         const KPList<Element> &list() const;
  52.         int size() const;
  53.         bool is_empty() const;
  54.         bool contains(const KPSet &set) const;
  55.         bool contains(const Element &element) const;
  56.         KPSet all_such_that(bool (*f)(const Element &)) const;
  57.         KPSet &clear();
  58.     protected:
  59.         KPSortableList<Element> my_list;
  60. };
  61.  
  62. /****************************************************************************/
  63.  
  64. template <class Element>
  65. inline
  66. KPSet<Element>::KPSet(): my_list()
  67. { /* do nothing */ }
  68.  
  69. /****************************************************************************/
  70.  
  71. template <class Element>
  72. inline
  73. KPSet<Element>::KPSet(const KPSet<Element> &set): my_list(set.my_list)
  74. { /* do nothing */ }
  75.  
  76. /****************************************************************************/
  77.  
  78. template <class Element>
  79. inline
  80. KPSet<Element>::KPSet(const KPList<Element> &list)
  81. {
  82.     *this = list;
  83. }
  84.  
  85. /****************************************************************************/
  86.  
  87. template <class Element>
  88. inline
  89. KPSet<Element>::KPSet(const Element &element): my_list(element)
  90. { /* do nothing */ }
  91.  
  92. /****************************************************************************/
  93.  
  94. template <class Element>
  95. inline
  96. KPSet<Element>::~KPSet()
  97. {
  98.     my_list.clear();
  99. }
  100.  
  101. /****************************************************************************/
  102.  
  103. template <class Element>
  104. inline
  105. KPSet<Element>::operator KPList<Element>() const
  106. {
  107.     return my_list;
  108. }
  109.  
  110. /****************************************************************************/
  111.  
  112. template <class Element>
  113. inline KPSet<Element>
  114. KPSet<Element>::operator+(const KPSet<Element> &set) const
  115. {
  116.     KPSet<Element> new_set(*this);
  117.     new_set += set;
  118.     return new_set;
  119. }
  120.  
  121. /****************************************************************************/
  122.  
  123. template <class Element>
  124. inline KPSet<Element>
  125. KPSet<Element>::operator+(const Element &element) const
  126. {
  127.     KPSet<Element> new_set(*this);
  128.     new_set += element;
  129.     return new_set;
  130. }
  131.  
  132. /****************************************************************************/
  133.  
  134. template <class Element>
  135. KPSet<Element> &
  136. KPSet<Element>::operator+=(const KPSet<Element> &set)
  137. {
  138.     if (this == &set)
  139.         return *this;
  140.  
  141.     KPIterator<Element> a(my_list);
  142.     KPReadOnlyIterator<Element> b(set.my_list);
  143.  
  144.     while (b.ptr()) {
  145.         while (a.ptr() && *a < *b)
  146.             a++;
  147.         if (!a.ptr()) {
  148.             for (; b.ptr(); b++)
  149.                 my_list.add_to_tail(*b);
  150.         }
  151.         else {
  152.             if (*a == *b)
  153.                 a++;
  154.             else
  155.                 a.insert_before_current(*b);
  156.             b++;
  157.         }
  158.     }
  159.  
  160.     return *this;
  161. }
  162.  
  163. /****************************************************************************/
  164.  
  165. template <class Element>
  166. KPSet<Element> &
  167. KPSet<Element>::operator+=(const Element &element)
  168. {
  169.     KPIterator<Element> iter(my_list);
  170.  
  171.     // Start looking from the end of the list, in case the elements are
  172.     // being added in a